package algorithms.sorts;

import algorithms.Utils;

import java.util.*;

public class QuickSort {
    public static void main(String[] args) throws InterruptedException {
        //int[] arr = {48, 99, 6, 57, 42, 60, 72, 83, 73, 88, 85};
        while (true) {
            int[] arr = Utils.randomArray(10000);
            long start = System.currentTimeMillis();
            //quickSortIterative(arr);
            quickSortRecursive(arr);
            System.out.println(System.currentTimeMillis() - start);
            // System.out.println(Arrays.toString(arr));
            System.out.println(Utils.isAscend(arr));
            Thread.sleep(1000);
        }

    }


    public static void quickSortRecursive(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int from, int to) {
        if (from == to) {
            return;
        }
        int low = adjust2(arr, from, to);
        if (low > from) {
            quickSort(arr, from, low - 1);
        }
        if (low < to) {
            quickSort(arr, low + 1, to);
        }
    }

    private static int adjust(int[] arr, int from, int to) {

        int low = from;
        int mid = (from + to) / 2;
        int base = arr[mid];
        Utils.swap(arr, low, mid);
        int high = to;
        boolean right = true;
        while (low < high) {
            if (right) {
                if (arr[high] < base) {
                    arr[low] = arr[high];
                    right = false;
                    low++;
                } else high--;
            } else {
                if (arr[low] > base) {
                    arr[high] = arr[low];
                    right = true;
                    high--;
                } else low++;
            }
        }
        //System.out.println(Arrays.toString(arr) + mid);
        arr[low] = base;
        return low;
    }

    private static int adjust2(int[] arr, int from, int to) {

        int low = from;
        int mid = (from + to) / 2;
        int base = arr[mid];
        Utils.swap(arr, low, mid);
        int high = to;
        out:
        while (low < high) {
            while (arr[high] > base) {
                high--;
                if (low >= high) break out;
            }
            arr[low] = arr[high];
            low++;
            if (low >= high) break;

            while (arr[low] < base) {
                low++;
                if (low >= high) break out;
            }
            arr[high] = arr[low];
            high--;
        }
        arr[low] = base;
        return low;
    }

    /**
     * 非递归实现
     */
    public static void quickSortIterative(int[] arr) {

        Deque<int[]> stack = new ArrayDeque<>();

        stack.push(new int[]{0, arr.length - 1});
        while (!stack.isEmpty()) {
            int[] section = stack.pop();
            int from = section[0];
            int to = section[1];
            int low = adjust(arr, from, to);

            if (low > from) {
                stack.push(new int[]{from, low - 1});
            }
            if (low < to) {
                stack.push(new int[]{low + 1, to});
            }
        }

    }
}
